package leetcode101.search_problem.bfs;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code3
 * @Description 126. Word Ladder II
 * A transformation sequence from word beginWord to word endWord using a 
 * dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
 *
 * Every adjacent pair of words differs by a single letter.
 * Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
 * sk == endWord
 * Given two words, beginWord and endWord, and a dictionary wordList, 
 * return all the shortest transformation sequences from beginWord to endWord,
 * or an empty list if no such sequence exists.
 * Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].
 *
 * Example 1:
 *
 * Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 * Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
 * Explanation: There are 2 shortest transformation sequences:
 * "hit" -> "hot" -> "dot" -> "dog" -> "cog"
 * "hit" -> "hot" -> "lot" -> "log" -> "cog"
 * Example 2:
 *
 * Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
 * Output: []
 * Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-06 9:51
 */
public class Code3 {

    public static void main(String[] args) {
        String beginWord = "red";
        String endWord = "tax";
        List<String> wordList = Arrays.asList("ted","tex","red","tax","tad","den","rex","pee");
        findLadders(beginWord, endWord, wordList);
    }

    static class Node {
        String word;
        Node prev;
        Node(String word, Node prev) {
            this.word = word;
            this.prev = prev;
        }
    }

    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

        List<List<String>> res = new ArrayList<>(); // 返回结果
        HashMap<String, Integer> wordId = new HashMap<>(); // 做单词和ID的映射关系
        List<String> idWord = new ArrayList<>(); // 因为不能根据value找key，所以再创建一个ID和单词的映射关系
        List<String> check = new ArrayList<>(); // 在BFS中用作判断结点是否被遍历过
        List<Node> path = new ArrayList<>(); // BFS中保存路径
        int initialId = 0; // 初始化ID
        /*
        首先将所有字典中的单词建立映射关系
         */
        for (String w : wordList) {
            if (!wordId.containsKey(w)) {
                wordId.put(w, initialId);
                idWord.add(initialId++, w);
            }
        }
        /*
        如果beginWord不存在字典中的话，加入
         */
        if (!wordId.containsKey(beginWord)) {
            wordId.put(beginWord, initialId);
            idWord.add(initialId, beginWord);
        }
        /*
        如果endWord不存在wordList中的话返回空值
         */
        if (!wordId.containsKey(endWord)) {
            return new ArrayList<>();
        }

        int[][] matrix = new int[wordId.size()][wordId.size()]; // 图

        for (int i = 0; i < wordId.size(); i++) { // 构建图
            for (int j = i + 1; j < wordId.size(); j++) {
                if (transformCheck(idWord.get(i), idWord.get(j))) {
                    matrix[i][j] = 1;
                    matrix[j][i] = 1;
                }
            }
        }

        Deque<Node> queue = new LinkedList<>();

        queue.offer(new Node(beginWord, null));

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node head = queue.poll();
                if (endWord.equals(head.word)) {
                    path.add(head);
                    continue;
                }
                if (!check.contains(head.word) || (check.contains(head.word) && !queue.isEmpty() && head.word.equals(queue.getLast().word))) { // 该中间节点没被检查过的话就把所有的可以接龙的单词放入队列中
                    check.add(head.word);
                    for (int j = 0; j < wordId.size(); j++) {
                        if (matrix[wordId.get(head.word)][j] == 1 && !check.contains(idWord.get(j))) {
                            queue.offer(new Node(idWord.get(j), head));
                        }
                    }
                }
            }
            if (path.size() > 0) {
                break;
            }
        }

        for (Node n : path) {
            List<String> temp = new ArrayList<>();
            while (n != null) {
                temp.add(0, n.word);
                n = n.prev;
            }
            res.add(temp);
        }

        return res;
    }

    private static boolean transformCheck(String s1, String s2) { // 判断两个字符串能否符合接龙条件
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }

}
/*
思路就是将所有可以经过一个字母变化的结点相连组成一个图
然后对这个图进行广度优先遍历，输出得到的结果
 */